package example2;

//152. 乘积最大子数组
public class LeetCode152 {
    public static void main(String[] args) {
        int[] nums = {-4,-3,-2};
        System.out.println(new Solution152().maxProduct(nums));
    }
}

class Solution152 {
    /**
     * 方法二：方法一的空间优化，因为每个元素只会用到上一个元素的最大最小值，所以可以用两个变量来存储两个最值，
     * 然后每次遍历的时候比较最值即可。
     */
    public int maxProduct(int[] nums) {
        int max = nums[0];
        int nowMax = nums[0];
        int nowMin = nums[0];
        int tempMax = nowMax;
        int tempMin = nowMin;
        for(int i=1;i<nums.length;i++){
            tempMax = nowMax;
            tempMin = nowMin;
            nowMax = Math.max(tempMin * nums[i],Math.max(tempMax * nums[i],nums[i]));
            nowMin = Math.min(tempMin * nums[i],Math.min(tempMax * nums[i],nums[i]));
            if(max < nowMax) max = nowMax;
        }
        return max;
    }

    /**
     * 方法一：动态规划     对于这种要求连续的子数组的，动态规划数组可以记录以第i个元素结尾的子数组的最值状态值
     * 两个数组，dpMax用来存储以第i个元素结尾的连续子数组乘积的最大值；dpMin用来存储以第i个元素结尾的连续子数组的乘积的最小值。
     * 因为数组中有负数，所以有可能有，在nums[i]为负时，如果只用dpMax来相乘等操作的话，那么得到的最大值就不准确，
     * nums[i]为负，同时dpMax[i-1]为正，dpMin[i-1]为负，那么dpMax[i]==dpMin[i-1] * nums[i]，所以也需要保存最小值。
     * 例如：2,3,4,-1,-2。如果只有dpMax的话，那么到-1时的dpMax就是-1，此时到-2时如果只跟dpMax相乘的话，那么-2的dpMax就是2，
     * 这种情况下整个数组的最大乘积子数组的值就是24。但其实不是，实际-2的dpMax应该为48，就是通过-1的dpMin * -2得来的，
     * 所以要记录并操作最小值。
     */
    public int maxProduct1(int[] nums) {
        int[] dpMax = new int[nums.length];
        int[] dpMin = new int[nums.length];
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];
        int max = dpMax[0];
        for(int i=1;i<nums.length;i++){
            dpMax[i] = Math.max(dpMin[i-1] * nums[i],Math.max(dpMax[i-1] * nums[i],nums[i]));
            dpMin[i] = Math.min(dpMin[i-1] * nums[i],Math.min(dpMax[i-1] * nums[i],nums[i]));
            if(max < dpMax[i]) max = dpMax[i];
        }
        return max;
    }
}
